package com.wj.algorithm.lintcode;

import java.util.Arrays;

public class P82 {
    /*
     * @param A: An integer array
     * @return: An integer
     */
    public int singleNumber(int[] A) {
        if(A == null || A.length < 1) {
            return 0;
        }
        int len = A.length;
        if(len == 1) {
            return A[0];
        }
        //排序
        Arrays.sort(A);
        //元素值游标
        long preItemValue = Long.MAX_VALUE;
        for(int i = 0; i < len; i ++) {
            //元素遍历，遇到不同
            if(i > 0 && preItemValue < Long.MAX_VALUE && preItemValue != A[i]) {
                //当前不同的，下标是偶数，则实际是奇数个，则返回当前数值
                if(i % 2 == 0) {//偶数
                    return A[i];
                } else {//下标是奇数，实际是偶数，则返回上一个
                    return (int) preItemValue;
                }
            }
            preItemValue = A[i];
            if(i % 2 == 1) {//奇数下标的话，下一个从新开始，赋值默认值
                preItemValue = Long.MAX_VALUE;
            }
        }
        //返回最后一个元素，因为前面遍历结束未找到落单
        return (int) preItemValue;
    }
    
    public static void main(String[] args) {
        System.out.println(new P82().singleNumber(new int[]{1,2,2,1,3,4,3}));
//        System.out.println(new P82().singleNumber(new int[]{7,10001,10002,10003,10001,10002,10003,10004,7,10004,91985345,2,2,3,4,5,5,4,3,11,91985345}));
    }
}
